// UVa136 Ugly Numbers
// 刘汝佳
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
  const int coeff[3] = {2, 3, 5};
  priority_queue<LL, vector<LL>, greater<LL> > pq;
  set<LL> s;
  pq.push(1), s.insert(1);
  LL x;
  for (int i = 1; x = pq.top(), pq.pop(), x; i++) {
    if (i == 1500) {
      cout << "The 1500'th ugly number is " << x << ".\n";
      break;
    }
    for (int j = 0; j < 3; j++) {
      LL x2 = x * coeff[j];
      if (!s.count(x2)) s.insert(x2), pq.push(x2);
    }
  }
  return 0;
}
/*
算法分析请参考: 《入门经典-第2版》例题5-7。
注意priority_queue::top()默认是取最大值，如果取最小值就需要改变其泛型参数
同类题目:
*/
// 24456866 136 Ugly Numbers  Accepted  C++11 0.000 2020-01-22 14:18:42